# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    def isSubtree(self, s, t):
        """
        :type s: TreeNode
        :type t: TreeNode
        :rtype: bool
        """
        if not s:
            return False
        if self.compare(s,t):
            return True
        return self.isSubtree(s.left,t) or self.isSubtree(s.right,t)

    def compare(self,s,t):
        if not s and not t :
            return True
        elif (not s and t) or (s and not t ):
            return False
        else:
            if s.val == t.val:
                self.compare(s.left ,t) and self.compare(s.right ,t)
            else:
                return False




    #     if not s:
    #         return False
    #     if self.compare(s,t):
    #         return True
    #     return self.isSubtree(s.left,t) or self.isSubtree(s.right,t)
    #
    # def compare(self,s,t):
    #     if s == None and t ==None:
    #         return True
    #     elif (s == None and t != None or s != None and t == None):
    #         return False
    #     else:
    #         if s.val != t.val:
    #             return False
    #         elif self.compare(s.left ,t.left) and self.compare(s.right ,t.right):
    #             return True
    #         else:
    #             return False















m1 = TreeNode(3)
m1.left = TreeNode(4)
m1.right = TreeNode(5)
m1.left.left = TreeNode(1)
m1.left.right = TreeNode(2)


m = TreeNode(4)
m.left = TreeNode(1)
m.right = TreeNode(2)

s = Solution()

t = s.isSubtree(m1,m)
print(t)
